package com.cuz.daileetcode.bat100;

public class 两地派遣司机让所有司机收入最大 {
    public static void main(String[] args) {
        int[][] ints = {{1, 10}, {10, 1}, {5, 1}, {3, 6}};
        System.out.println(solution1(ints, 2));
        System.out.println(solution2(ints, 2));
    }

    /***
     * 司机N*2人，
     * 第i司机去A地收入 incomes[i][0]
     * 第i司机去B地收入 incomes[i][1]
     * @param incomes
     * @param N
     * @return 最大收益
     */
    public static int solution1(int[][] incomes, int N) {
        return process1(incomes, N, 0);
    }

    /***
     *     curIndex...以后的司机分配 获得最大的收益是多少，
     *     restForA A地区还可分配多少个
     */
    private static int process1(int[][] incomes, int restForA, int curIndex) {
        if (curIndex == incomes.length) {
            return 0;
        }
        //A地无法分配了 只能去B地区
        if (restForA == 0) {
            return process1(incomes, restForA, curIndex + 1) + incomes[curIndex][1];
        }
        //当前司机去A
        int curDriverToA = process1(incomes, restForA - 1, curIndex + 1) + incomes[curIndex][0];
        //当前司机去B
        int curDriverToB = process1(incomes, restForA, curIndex + 1) + incomes[curIndex][1];
        return Math.max(curDriverToA, curDriverToB);
    }


    public static int solution2(int[][] incomes, int N) {
        int driverCount = incomes.length;
        int[][] dp = new int[driverCount][N + 1];
        for (int count = driverCount - 1; count >= 0; count--) {
            dp[count][0] = incomes[count][1];
            if (count != driverCount - 1) {
                dp[count][0] += dp[count + 1][0];
            }
        }
        for (int i = incomes.length - 2; i >= 0; i--) {
            int[] loopDriver = incomes[i];
            for (int n = N; n >= 0; n--) {
                dp[i][n] = loopDriver[1] + dp[i + 1][n];
                if (n != 0) {
                    dp[i][n] = Math.max(loopDriver[0] + dp[i + 1][n - 1], dp[i][N]);
                }
            }
        }
        return dp[0][N];
    }


}
